#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <list>

class Graph
{
private:
    // 顶点个数
    int vertices;
    // 边表adjacencyList是一个向量，每个元素是一个存储与相应顶点相邻的顶点的向量
    // std::vector<std::vector<int>> adjacencyList;

    // 邻接表
    std::vector<std::list<int>> adjacencyList; 
public:
    Graph(int vertices);
    ~Graph();
    void addEdge(int v, int w);
    void DFS(int startVertex);
    void BFS(int startVertex);
};

Graph::Graph(int vertices)
{
    this->vertices = vertices;
    // 调整外层vector的大小为顶点个数
    adjacencyList.resize(vertices);
}

Graph::~Graph()
{
    std::cout << "~Graph ..." << std::endl;
}

// 对称矩阵
void Graph::addEdge(int v, int w) {
    adjacencyList[v].push_back(w);
    adjacencyList[w].push_back(v);
}

void Graph::DFS(int startVertex) {
    std::vector<bool> visited(vertices, false);
    std::stack<int> stack;

    visited[startVertex] = true;
    stack.push(startVertex);

    while (!stack.empty())
    {
        int currentVertex = stack.top();
        stack.pop();

        std::cout << currentVertex << " ";

        for (auto &&neighbor : adjacencyList[currentVertex])
        {
            if (!visited[neighbor])
            {
                visited[neighbor] = true;
                stack.push(neighbor);
            }
            
        }
    }

    std::cout << std::endl;
}

void Graph::BFS(int startVertex) {
    std::vector<bool> visited(vertices, false);
    std::queue<int> queue;

    visited[startVertex] = true;
    queue.push(startVertex);

    while (!queue.empty())
    {
        int currentVertex = queue.front();
        queue.pop();

        std::cout << currentVertex << " ";

        for (auto &&neighbor : adjacencyList[currentVertex])
        {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.push(neighbor);
            }
        }
        
    }
    std::cout << std::endl;
}


int main() {
    Graph g(6);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(2, 5);
    g.addEdge(4, 3);

    std::cout << "DFS starting from vertex 0: ";
    g.DFS(0);

    std::cout << "BFS starting from vertex 0: ";
    g.BFS(0);


    return 0;
}